package cn.corffen.test.algorithm.java;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class DoublePointJava {
    public static void main(String[] args) {
        System.out.println("hello world!");
    }

    public int[] twoSum(int[] numbers, int target) {
        int lo = 0;
        int hi = numbers.length - 1;
        while (lo < hi) {
            int sum = numbers[lo] + numbers[hi];
            if (sum > target) {
                hi--;
            } else if (sum < target) {
                lo++;
            } else {
                return new int[]{lo + 1, hi + 1};
            }
        }
        return new int[]{-1, -1};
    }

    /**
     * 最小滑动窗口
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        int[] chars = new int[128];
        boolean[] flags = new boolean[128];
        //flags判断是否包含t中的元素
        //chars数组记录了t中元素的个数
        for (int i = 0; i < t.length(); i++) {
            flags[t.charAt(i)] = true;
            ++chars[t.charAt(i)];
        }

        int cnt = 0, l = 0, min_l = 0, min_size = s.length() + 1;
        for (int r = 0; r < s.length(); r++) {
            //移动右指针的过程中,如果包含t中的元素
            if (flags[s.charAt(r)]) {
                //将t中的元素个数自减,然后统计数量+1
                if (--chars[s.charAt(r)] >= 0) {
                    ++cnt;
                }
//当统计的数量等于t中元素的个数时,说明包含了t,此时移动左指针,缩减空间
                while (cnt == t.length()) {
                    if (r - l + 1 < min_size) {
                        min_l = l;
                        min_size = r - l + 1;
                    }
                    //如果包含左指针,并且左指针自增之后大于0,说明当前左指针的元素时唯一的一个
                    //此时将cnt自减,那么就不会再满足循环条件
                    if (flags[s.charAt(l)] && ++chars[s.charAt(l)] > 0) {
                        --cnt;
                    }
                    //移动左指针
                    ++l;
                }
            }
        }
        //最小size默认设置为s的长度+1,用于判断是否包含t
        return min_size > s.length() ? "" : s.substring(min_l, min_l + min_size);
    }

    public boolean judgeSquareSum(int c) {
        int start = 0;
        int end = (int) Math.sqrt(c);
        while (start <= end) {
            int sum = start * start + end * end;
            if (sum == c) {
                return true;
            } else if (sum < c) {
                start++;
            } else {
                end--;
            }
        }
        return false;
    }

    public boolean validPalindrome(String s) {
        int start = 0;
        int end = s.length() - 1;
        while (start < end) {
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else {
                boolean flag1 = true;
                boolean flag2 = true;
                for (int i = start, j = end - 1; i < j; i++, j--) {
                    char c1 = s.charAt(i);
                    char c2 = s.charAt(j);
                    if (c1 != c2) {
                        flag1 = false;
                        break;
                    }
                }

                for (int i = start + 1, j = end; i < j; i++, j--) {
                    char c3 = s.charAt(i);
                    char c4 = s.charAt(j);
                    if (c3 != c4) {
                        flag2 = false;
                        break;
                    }
                }
                return flag1 || flag2;
            }
        }
        return true;
    }

    public String findLongestWord(String s, List<String> d) {
        Collections.sort(d, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length() != o2.length() ? o2.length() - o1.length() : o1.compareTo(o2);
            }
        });

        for (String x : d) {
            if (isSubSequence(x, s)) {
                return x;
            }
        }
        return "";
    }

    public boolean isSubSequence(String x, String y) {
        int j = 0;
        for (int i = 0; i < y.length() && j < x.length(); i++) {
            if (y.charAt(i) == x.charAt(j)) {
                j++;
            }
        }
        return j == x.length();
    }
}
